This invention relates to creating a digital circuit. More particularly, the invention relates to converting an algorithm rendered in a programming language into an actual hardware implementation consisting of the digital circuit.
Various persons have previously attempted to address the long-felt need for an easy approach to creating hardware designs. The prior art evidences two divergent approaches for designing actual implementations of digital hardware.
One prior art approach recognizes that the development of digital hardware would be available to a wider population if hardware designs could be rendered in a standard high-level programming language, which is more universally known, easier to use, and more frequently employed than HDLs. One such high-level programing language is ANSI C. Others, many of which have several extensions, are: APL, Ada, Algol, B, Basic, Kernighan and Ritchie C, C++, CLOS, COBOL, Clu, Common Lisp, Coral, Dylan, Eiffel, Emacs Lisp, Forth, Fortan, IDL, Icon, Java, Jovial, Lisp, LOGO, ML, Modula, Oberon, Objective C, PL/I, PL/M, Pascal, Postscript, Prolog, Python, RTL, Rexx, SETL, Simula, Sather, Scheme, Smalltalk, Standard ML, TCL, and TRAC.
Prior art attempts to base computer aided hardware design tools on high-level programing languages have generally suffered from a number of shortcomings. In order to represent an algorithm in a high-level language, the designer must typically sacrifice direct control over the circuits generated by the associated design tools. Because the high-level language has no mechanism to represent specially constructed adders, multipliers and the like, the resulting tool-generated circuit typically has poor performance relative to what a hardware designer could achieve given the same algorithm. Furthermore, the tool-generated circuits may be inefficiently large compared to a human-designer created circuit. This results from the fact that hardware generated using prior art computer aided hardware design tools is typically based on simple line-by-line, table-driven translation and lacks the global optimizations that can be perceived by the human designer. In addition, the high-level language may lack the ability to specify non-standard sized registers, bit-serial communication paths and other design constructs known to produce smaller designs. Finally, in an attempt to approach human-designer quality results, the user of the high-level language based toolset might have to resort to a much lower-level algorithm specification, thus sacrificing the clarity of representation that is a primary benefit of this prior art toolset.
The inability of the prior art to generate efficient circuits is further illustrated by the following example. In this example, an algorithm to sum ten numbers is considered. An important aspect of the numbers to be summed in this example is that they represent student exam scores and can assume values in the range of 0 to 100 inclusive. The maximum value of the exam score total, which is specified to be the sum of ten exam scores, is thus 10*100=1000. This algorithm, coded in the high-level conventional C-language, is as follows:
/* source code A */
unsigned char exam_scores[10];
unsigned short total_exam_scores( ) {
unsigned short total=0;
unsigned int i;
for (i=0;i less than 10;i++)
total+=exam_scores[i];
return total;
}
FIG. 7 shows a digital circuit 700 that may be generated by inputting the source code A into a prior art compiler. In this and subsequent circuit diagrams, a clocked register is denoted by a rectangular box with a double line at its input and with the xcex94 symbol inside to denote a delay of one clock cycle. Furthermore, in circuit 700 and subsequent circuit diagrams, only the datapath logic is shown, with control logic like clocking and memory address sequencing omitted for the sake of clarity. In the source code A, an 8-bit xe2x80x9cunsigned charxe2x80x9d is used for the xe2x80x9cexam_scoresxe2x80x9d variable, since xe2x80x9cunsigned charxe2x80x9d is the smallest data type available in C that can still hold the maximum exam score of 100. A 16-bit xe2x80x9cunsigned shortxe2x80x9d is used for the xe2x80x9ctotalxe2x80x9d variable, since this is the smallest data type that can hold the maximum exam score total of 1000. Based on this coding, a prior art compiler would generate the circuit 700 consisting of an 8-bit wide exam score memory 710, a 16-bit adder 720 and a 16-bit xe2x80x9ctotalxe2x80x9d register 730. The circuit 700, however, is far larger than optimal, because the smallest available variable sizes are larger than necessary, which results in an inefficient hardware realization.
A high-level language, i.e., PASCAL, provides the ability by way of its scalar subrange data types to specify a variable""s set of assumable values, and hence its bit-width, with greater specificity than the conventional C-language. However, PASCAL has not been implemented in an algorithm-to-hardware toolset to provide optimal circuit configurations. Because of these listed shortcomings, the attempts at creating an effective tool for designing hardware using a high-level programming language have not achieved widespread use.
A second prior art approach to creating designs for digital hardware has been to create a specific hardware description language (HDL). Various commercially available HDLs have been developed, such as Verilog, VHDL, ABEL, CUPL, AHDL, MACHX, and PALASM. After a hardware design is rendered in an HDL, the HDL design is processed into a gate-level or cell-level netlist representation using one of various hardware or manufacturer-specific synthesis programs to interpret the HDL design. Then, the netlist representation is reduced to an actual hardware realization using conventional physical design tools.
HDLs and their associated computer-aided design tools have been created to be used by hardware designers and require a level of expertise in the use of the particular HDL being employed to render a hardware design. Because HDLs are difficult to learn and use, only persons who frequently design hardware typically use them. If a circuit application arises in which an HDL-representation of the algorithm is justified, the vast majority of persons must retain an expert or confront the difficult task of learning an HDL. Furthermore, these HDLs are not typically universal for the design of all target hardware technologies, since many HDLs are supported by only a single or a limited number of hardware manufacturers. Consequently, even experienced users of an HDL may not be sufficiently familiar with other HDLs to be able to render a design that can be implemented in a variety of hardware systems from a number of different hardware manufacturers.
HDLs permit a much more detailed control over the resulting hardware implementation, but often by sacrificing the clarity and supportability of the algorithm. To further illustrate this shortcoming of conventional HDLs, the previous problem of summing 10 exam scores is reconsidered. In an attempt to create a more efficient hardware realization, the algorithm specification is modified by including a language-feature present in prior art HDLs such as Verilog and VHDL, namely the ability to specify exact bit-widths of variables. Using one of a number of possible syntaxes, an integer variable whose value representation is constrained to exactly N bits is defined using the datatype xe2x80x9cintNxe2x80x9d. The revised algorithm for summing ten exam scores is coded in the source code B as follows:
/* source code B */
unsigned int7 exam_scores[10];
unsigned int10 total_exam_scores( ) {
unsigned int10 total=0;
unsigned int i;
for (i=0;i less than 10;i++)
total +=exam_scores[i];
return total;
}
The source code B uses the added bit-width language feature to specify a smaller size for the xe2x80x9cexam_scoresxe2x80x9d and the xe2x80x9ctotalxe2x80x9d variables. In particular, a 7-bit integer type xe2x80x9cunsigned int7xe2x80x9d is the smallest data type available that can hold the maximum exam score of 100. Similarly, an xe2x80x9cunsigned int10xe2x80x9d is the smallest data type that can hold the maximum exam score total of 1000. Based on this coding, a prior art compiler would generate a circuit as shown in FIG. 8 consisting of a 7-bit wide exam score memory 810, a 10-bit adder 820 and a 10-bit xe2x80x9ctotalxe2x80x9d register 830. The reduced size circuit 800 represents an improvement over the circuit 700 (FIG. 7), because the circuit 800 is optimized for the data to be summed and is thus smaller. This improvement, however, comes at a price. First of all, the burden of calculating the proper bit-width of the variables has been forced on the user, and there is certainly the possibility of miscalculation. In addition, the relationship between the required bit-width of the xe2x80x9ctotalxe2x80x9d variable and the number and maximum value of the exam scores is lost. For example, assume that an exam is subsequently created that has a 10-point extra credit question. A support engineer directed to update source code B might inspect the program and conclude that it requires no changes, since the 7-bit xe2x80x9cexam_scorexe2x80x9d width is sufficient to hold the new larger maximum of 110. However, circuit 800 would fail to calculate the proper total value in all circumstances, since the new maximum 10-exam total is 1100, which exceeds the value that can be held by the 10-bit total register 830. Thus, the use of the bit-width language feature present in many conventional HDLs can obscure important variable relationships in an algorithm and can lead to programming errors.
In one respect, the invention includes a method of converting code to a hardware realization. The method comprises steps of receiving user code including at least one algorithm specification, at least one data representation specification, and at least one data communication specification; and compiling the user code, wherein the user code is used to create a digital circuit.
In another respect, the invention includes another method of converting code to a hardware realization. The method comprises steps of receiving user code; identifying variables used in an operation in the user code, the operation including at least one operator, identifying a set of assumable values for each of the identified variables; calculating a set of assumable values for other variables holding the results of the operation based on the identified set of assumable values; and compiling the user code, wherein the user code is used to create a digital circuit.
In yet another respect, the invention includes a system operable to create a digital circuit. The system comprises a compiler compiling user code, the user code including at least one algorithm specification, at least one data representation specification, and at least one data communication specification; and a digital circuit created based on the compiled user code.
The methods of the invention include steps that may be performed by computer-executable instructions executing on a computer-readable medium.
One embodiment of the present invention includes the independence of an algorithm description from the implementation-specific details of data representation and communication. As a hardware designer explores the implementation design space (e.g., generates various hardware realizations to produce an optimal hardware realization), the designer is not required to completely recode and obscure the algorithm to force the compiler to generate the specific structures that support a particular choice of data representation and communication.
Other certain embodiments of the present invention include the ability to precisely specify the set of assumable values for variables (i.e., the variable""s assumable value set) and automatically deduce the assumable value set for some variables. Those skilled in the art will appreciate these and other aspects of various embodiments of the invention upon reading the following detailed description with reference to the below-listed drawings.